package Arrays;

public class _561_ArrayPartitionI {
    //超时
    public int arrayPairSum(int[] nums) {
        int length = nums.length;
        QuickSort(nums,0,length-1);
        int sum = 0;
        for(int i=0;i<length;i+=2){
            sum +=nums[i];
        }
        return sum;
    }

    public void QuickSort(int R[], int s, int t)
    {
        int i = s, j = t;
        int tmp;
        if (s<t)                 //区间内至少存在两个元素的情况
        {
            tmp = R[s];         //用区间的第1个元素作为基准
            while (i != j)      //从区间两端交替向中间扫描,直至i=j为止
            {
                while (j>i && R[j] >= tmp)
                    j--;        //从右向左扫描,找第1个小于tmp的R[j]
                R[i] = R[j];        //找到这样的R[j],R[i]和R[j]交换
                while (i<j && R[i] <= tmp)
                    i++;        //从左向右扫描,找第1个大于tmp的元素R[i]
                R[j] = R[i];        //找到这样的R[i],R[i]和R[j]交换
            }
            R[i] = tmp;
            QuickSort(R, s, i - 1); //对左区间递归排序
            QuickSort(R, i + 1, t); //对右区间递归排序
        }
    }
}
